package leetcode;

public class ReverseLinkedList206 {
    // 头插法 从头开始遍历每个节点,插入新节点的头
    public static ListNode reverseList1(ListNode o1) {
        ListNode pointer = o1;
        ListNode head = null;
        while (pointer != null) {
            head = new ListNode(pointer.val, head);
            pointer = pointer.next;
        }
        return head;
    }

    // 面向过程解题
    public static ListNode reverseList5(ListNode o1) {
        ListNode n1 = null;
        ListNode o2 = null;
        while (o1 != null) {
            o2 = o1.next;
            o1.next = n1;
            n1 = o1;
            o1 = o2;
        }
        return n1;
    }

    // 三指针解题
    public static ListNode reverseList4(ListNode o1) {
        if (o1 == null || o1.next == null) {
            return o1;
        }
        ListNode n1 = o1;
        ListNode o2 = o1.next;
        while (o2 != null) {
            o1.next = o2.next;
            o2.next = n1;
            n1 = o2;
            o2 = o1.next;
        }
        return n1;
    }

    // 递归解题
    public static ListNode reverseList2(ListNode o1) {
        if (o1 == null || o1.next == null) {
            return o1;
        }
        ListNode newhead = reverseList2(o1.next);
        o1.next.next = o1; // 递归出口后 回到前一个方法 此时指向 原链表末尾-1
        o1.next = null; // 将next指向末尾切断 避免死循环
        return newhead;
    }

    // 转换成面向对象 通过集合类进行操作 removefirst addfirst
    public static ListNode reverseList3(ListNode o1) {
        List old = new List(o1);
        List n = new List(null);
        ListNode pointer = null;
        while ((pointer = old.removeFirst()) != null) {
            n.addFirst(pointer);
        }
        return n.head;
    }

    static class List {
        ListNode head;

        public List(ListNode head) {
            this.head = head;
        }

        public void addFirst(ListNode newNode) {
            newNode.next = head;
            head = newNode;
        }

        public ListNode removeFirst() {
            ListNode old = head;
            if (head != null) {
                head = head.next;
            }

            return old;
        }
    }

    public static void main(String[] args) {
        ListNode node6 = new ListNode(6, null);
        ListNode node5 = new ListNode(5, node6);
        ListNode node4 = new ListNode(4, node5);
        ListNode node3 = new ListNode(3, node4);
        ListNode node2 = new ListNode(2, node3);
        ListNode node1 = new ListNode(1, node2);
        System.out.println(node1);
        ListNode newNode = reverseList5(node1);
        System.out.println(newNode);

    }

    static class ListNode {
        public int val;
        public ListNode next;

        public ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }

        @Override
        public String toString() {
            ListNode pointer = this;
            StringBuilder sb = new StringBuilder();
            sb.append("{");
            while (pointer != null) {
                sb.append(pointer.val);
                if (pointer.next != null) {
                    sb.append(",");
                }
                pointer = pointer.next;
            }
            sb.append("}");
            return sb.toString();
        }


    }
}

